#include <stdio.h>
#include <stdlib.h>

struct PolyNode 
{
	int coef;
	int expon;
	struct PolyNode *link;
};


typedef struct PolyNode *Polynomial;
Polynomial P1, P2;
void Attach(int c,int e, Polynomial*pRear)
{
	Polynomial P;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = c;
	P->expon = e;
	P->link = NULL;
		
	(*pRear)->link = P;
	*pRear = P;
}

Polynomial ReadPoly()
{
	int N,c,e;
	Polynomial P,Rear, t;
	printf("请输入项数：");
	scanf("%d", &N);

	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear = P;
	while(N--)
	{	
		printf("请输入系数和指数：");
		scanf("%d %d",&c, &e);
		Attach(c, e, &Rear);
	}
	t = P;
	P = P->link;
	free(t);
	return P;
}

Polynomial Mult(Polynomial P1, Polynomial P2)
{
	Polynomial P, Rear, t1, t2, t;
	int c, e;
	if(!P1 || !P2)
	{
		return NULL;
	}
	t1 = P1, t2 = P2;
	
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear = P;
	while(t2)
	{
		Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
		t2 = t2->link;
	}
	t1 = t1->link;
	while(t1)
	{
		t2 = P2;
		Rear = P;
		while(t2)
		{
			e = t1->expon * t2->expon; 
			c = t1->coef * t2->coef;
			while(Rear->link && Rear->link->expon > e)
			{
				Rear = Rear->link;
			}
			if(Rear->link && Rear->link->expon == e)
			{
				if(Rear->link->coef + c)
				{
					Rear->link->coef +=c;
				}
				else
				{
					t = Rear ->link;
					Rear->link = t->link;
					free(t);
				}
			}
			else
			{
				t = (Polynomial)malloc(sizeof(struct PolyNode));
				t->coef = c;
				t ->expon = e;
				t->link = Rear->link;
				Rear->link = t;
				Rear = Rear->link;
			}
		}
		t1 = t1->link;
	}
	t2 = P;
	P = P->link;
	free(t2);
	return P;
}

//打印
void PrintPoly(Polynomial data)
{
	int flag = 0;

	if(!data)
	{
		printf("链表为空！\n");
		return ;
	}

	while(data)
	{	
		if(!flag)
		{
			flag = 1;
		}
		else
		{
			printf(" ");
		}
		printf("%dX^%d",data->coef,data->expon);
		data = data->link;
	}
	printf("\n");

}
 

int main()
{
	Polynomial P1, P2, PP, PS;
	P1 = ReadPoly();
	P2 = ReadPoly();
	PP = Mult(P1,P2);
	PrintPoly(PP);
	return 0;
}

